using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SurvivalStrategy
{
    public class PriorityQueue
    {
        public List<Request> list;
        public int Count { get { return list.Count; } } 

        public PriorityQueue()
        {
            this.list = new List<Request>();
        }

        private void BuildHeap()
        {
            int j, k;
            Request x;
            for (int i = 1; i <= list.Count; i++)
            {
                j = i;
                k = j / 2;
                x = list[i - 1];
                while ((k > 0) && (list[k - 1].Priority < x.Priority))
                {
                    list[j - 1] = list[k - 1];
                    j = k;
                    k = j / 2;
                }
                list[j - 1] = x;
            }
        }

        private void CollapseHeap()
        {
            int j, k, m;
            for (int i = list.Count; i > 1; i--)
            {
                Request temp = list[0];
                list[0] = list[i - 1];
                list[i - 1] = temp;

                j = 1;
                k = 2;
                while (k < i)
                {
                    if ((k + 1 < i) && (list[k + 1 - 1].Priority > list[k - 1].Priority))
                        m = k + 1;
                    else
                        m = k;
                    if (list[m - 1].Priority <= list[j - 1].Priority) break;
                    Request temp2 = list[j - 1];
                    list[j - 1] = list[m - 1];
                    list[m - 1] = temp2;
                    j = m;
                    k = j + j;
                }
            }
        }

        public void Sort()
        {
            BuildHeap();
            CollapseHeap();
        }

        public void Enqueue(Request e)
        {
            list.Add(e);
            int child = list.Count - 1;

            while ((child > 0) && (list[child].Priority > list[child / 2].Priority))
            {
                Request temp = list[child];
                list[child] = list[child / 2];
                list[child / 2] = temp;
                child = child / 2;
            }
        }

        public Request Dequeue()
        {
            int j, k, m;
            int i = list.Count;

            Request result = list[0];
            list[0] = list[i - 1];
            list[i - 1] = result; // zamienia aktywny element z pierwszym elementem
            j = 1; //element ktory edytujemy
            k = 2; //lewy syn
            while (k < i)
            {
                if ((k + 1 < i) && (list[k + 1 - 1].Priority > list[k - 1].Priority)) //patrzymy ktory syn jest wiekszy
                    m = k + 1;
                else
                    m = k;
                if (list[m - 1].Priority <= list[j - 1].Priority) break;//jezeli jestesmy wieksi od najwiekszego syna to jest czad
                Request temp2 = list[j - 1];
                list[j - 1] = list[m - 1];
                list[m - 1] = temp2;//jezeli nie to zamieniamy sie z synem
                j = m; //syn zostaje nami
                k = j + j; // dziecko syna i idziemy w dol kopca
            }

            list.Remove(list[list.Count - 1]);
            return result;
        }


        public Request Top()
        {
            if (list.Count > 0)
            {
                Request result = list[0];
                return result;
            }
            else return null;
        }

        public bool Empty()
        {
            return list.Count == 0;
        }

        public void Remove(Request request)
        {
            list.Remove(request);
            Sort(); 
        }
    }
}